package A_review.huawei_10_27;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

//TODO:2023/10/29 全排列 字母 可适用于有重复的字母
public class Class157 {

    List<String> ans = new LinkedList<>();
    StringBuilder sb = new StringBuilder();

    public String[] goodsOrder(String goods) {
        int len = goods.length();
        if (len == 1) {
            return new String[]{goods};
        }
        boolean[] record = new boolean[len];
        char[] chars = goods.toCharArray();
        Arrays.sort(chars);
        backTracking(chars,record);
        String[] ans1 = new String[ans.size()];
        ans.toArray(ans1);
        return ans1;
    }

    public void backTracking(char[] goods,boolean[] record) {
        if (sb.length()==goods.length) {
            ans.add(sb.toString());
        }
        for (int i = 0; i < goods.length; i++) {
            if (record[i]==true||(i>0&&goods[i]==goods[i-1]&&!record[i-1])){
                continue;
            }
            record[i]=true;
            sb.append(goods[i]);
            backTracking(goods,record);
            sb.deleteCharAt(sb.length() - 1);
            record[i]=false;
        }
    }

}
